package com.example.demo.leetcode.top100;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _73柱状图中最大的矩形
 * @description
 * @date 2023/06/26 10:02
 * <p>
 * ******************************************************
 */
public class _73柱状图中最大的矩形 {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        // 左边比当前小的元素
        int[] left_lower = new int[length];
        left_lower[0] = 0;
        // 右边比当前小的元素
        int[] right_lower = new int[length];
        right_lower[length - 1] = length - 1;

        label1:
        for (int i = 1; i < length; i++) {
            int j = i - 1;
            while (j >= 0) {
                if (heights[j] == heights[i]) {
                    left_lower[i] = left_lower[j];
                    continue label1;
                } else if (heights[j] < heights[i]) {
                    left_lower[i] = j + 1;
                    break;
                }
                j--;
            }
        }

        label2:
        for (int i = length - 2; i >= 0; i--) {
            int j = i + 1;
            while (j < length) {
                if (heights[j] == heights[i]) {
                    right_lower[i] = right_lower[j];
                    continue label2;
                } else if (heights[j] < heights[i]) {
                    break;
                }
                j++;
            }
            right_lower[i] = j - 1;
        }


        int max = 0;

        for (int i = 0; i < length; i++) {
            int item = (right_lower[i] - left_lower[i] + 1) * heights[i];
            max = Math.max(max, item);
        }
        return max;
    }


    public static void main(String[] args) {
        _73柱状图中最大的矩形 s = new _73柱状图中最大的矩形();
        System.out.println(s.largestRectangleArea(new int[]{1, 1}));
    }
}
